package com.lfg.leetcode.leetcode300;

import java.util.ArrayList;
import java.util.List;


public class No315countSmaller {
    public static void main(String[] args) {
        List<Integer> list = countSmaller(new int[]{5, 2, 6, 1});
        for (int ret : list) {
            System.out.println("[" + ret + "]");
        }
    }

    private static void sort(int[] nums, int[] smaller, int[] pos, int from, int to) {
        if (from >= to) {
            return;
        }
        int m = (from + to) / 2;
        sort(nums, smaller, pos, from, m);
        sort(nums, smaller, pos, m + 1, to);
        int[] merged = new int[to - from + 1];
        int i = from, j = m + 1, k = 0, jump = 0;
        while (i <= m || j <= to) {
            if (i > m) {
                jump++;
                merged[k++] = pos[j++];
            } else if (j > to) {
                smaller[pos[i]] += jump;
                merged[k++] = pos[i++];
            } else if (nums[pos[i]] <= nums[pos[j]]) {
                smaller[pos[i]] += jump;
                merged[k++] = pos[i++];
            } else {
                jump++;
                merged[k++] = pos[j++];
            }
        }
        for (int p = 0; p < merged.length; p++) {
            pos[from + p] = merged[p];
        }
    }

    public static List<Integer> countSmaller5(int[] nums) {
        int[] smaller = new int[nums.length];
        int[] pos = new int[nums.length];
        for (int i = 0; i < pos.length; i++) pos[i] = i;
        sort(nums, smaller, pos, 0, nums.length - 1);
        List<Integer> result = new ArrayList<>(nums.length);
        for (int i = 0; i < nums.length; i++) result.add(smaller[i]);
        return result;
    }


    public static List<Integer> countSmaller(int[] nums) {
        List<Integer> list = new ArrayList<>(nums.length);
        if (nums.length == 0) {
            return list;
        }
        int[] result = new int[nums.length];
        int[] addr = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            addr[i] = i;
        }
        mergerSort(nums, 0, nums.length - 1, result, addr);
        for (int i = 0; i < nums.length; i++) {
            list.add(result[i]);
        }
        return list;
    }

    public static void mergerSort(int[] array, int start, int end, int[] result, int[] addr) {
        if (end <= start) {
            return;
        }
        int length = end - start + 1;
        int mid = (start + end) / 2;
        mergerSort(array, start, mid, result, addr);
        mergerSort(array, mid + 1, end, result, addr);

        int i = start;
        int j = mid + 1;
        int index = 0;
        int[] ret = new int[length];

        int cnt = 0;
        while (i <= mid && j <= end) {
            if (array[addr[i]] <= array[addr[j]]) {
                result[addr[i]] += cnt;
                ret[index++] = addr[i++];
            } else {
                cnt++;
                ret[index++] = addr[j++];
            }
        }
        while (j <= end) {
            cnt++;
            ret[index++] = addr[j++];
        }
        while (i <= mid) {
            result[addr[i]] += cnt;
            ret[index++] = addr[i++];
        }
        for (i = 0; i < length; i++) {
            addr[i + start] = ret[i];
        }
    }


    public static List<Integer> countSmaller3(int[] nums) {
        List<Integer> list = new ArrayList<>(nums.length);
        if (nums.length == 0) {
            return list;
        }
        int[] result = new int[nums.length];
        int index = nums.length - 1;
        Node root = new Node(nums[index]);
        result[index--] = 0;
        for (int i = index; i >= 0; i--) {
            result[i] = root.insert(nums[i]);
        }
        for (int i = 0; i < nums.length; i++) {
            list.add(result[i]);
        }
        return list;
    }


    public static List<Integer> countSmaller2(int[] nums) {
        List<Integer> list = new ArrayList<>(nums.length);

        for (int i = 0; i < nums.length; i++) {
            int cnt = 0;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) {
                    cnt++;
                }
            }
            list.add(cnt);
        }

        return list;
    }


}

class Node {
    int val;
    int cnt;

    Node left;
    Node right;

    Node(int val) {
        this.val = val;
        this.cnt = 1;
    }


    public int insert(int val) {
        Node root = this;
        int ret = 0;
        while (true) {
            root.cnt++;
            if (val > root.val) {
                ret += root.cnt - 1;
                if (root.right != null) {
                    ret -= root.right.cnt;
                }
                if (root.right == null) {
                    root.right = new Node(val);
                    return ret;
                }
                root = root.right;
            } else {
                if (root.left == null) {
                    root.left = new Node(val);
                    return ret;
                }
                root = root.left;
            }
        }
    }


}
